#ifndef __PTREE_H__
#define __PTREE_H__

#include <sys/types.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "debug.h"

template<class T> class Table
{
protected:
  int dataCount;

public:
  Table () : dataCount (0) {}
  virtual ~Table () {}

  virtual T * fetch (void * key, size_t len) = 0;
  virtual T * lookup (void * key, size_t len) = 0;
  virtual T * search (void * key, size_t len) = 0;
  virtual bool remove (void * key, size_t len) = 0;
  virtual bool insert (void * key, size_t len, T * p) = 0;
  virtual int getCount () { return this->dataCount; }
  
  virtual void feInit () = 0;
  virtual void feNext () = 0;
  virtual bool feEnd () = 0;
  virtual T * feGet () = 0;
};



// **********************************************************************
// * Template Class: PTree
// **********************************************************************

const static u_int8_t bitmask[] =
  {0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff};

static const int  LINK_NULL    = 0x00;
static const int  LINK_0_OK    = 0x01;
static const int  LINK_1_OK    = 0x02;
static const int  LINK_BOTH_OK = 0x03;

template<class T> class PTreeNode;

//=========================================================================
template<class T> class PTree : public Table<T>
{
private:

  PTreeNode<T> root;
  PTreeNode<T> *ptr;
  void deleteNode (PTreeNode<T> * t);
  void branchNode (PTreeNode<T> * a, PTreeNode<T> * b);

  inline int MIN(int N1, int N2) { return (((N1) < (N2)) ? (N1) : (N2)); }
  inline u_int8_t CHECK_BIT(u_int8_t *K, int L) 
  { return ((((u_int8_t *)(K))[(L)/8] >> (7 - (L)%8)) & 1); }
  inline bool MATCH_KEY(u_int8_t * K1, u_int8_t * K2, int L)
  {
    return (((L >= 8) ? (memcmp ((u_int8_t*)(K1), (u_int8_t*)(K2), (L)/8) == 0) : 1 )
	    && (((L) % 8 > 0) ?					   
		((((u_int8_t*)(K1))[(L)/8] & bitmask[(L)%8]) ==	
		 (((u_int8_t*)(K2))[(L)/8] & bitmask[(L)%8])) : 1));
  }
  PTreeNode<T> * reHead (PTreeNode<T> * p);

public:
  PTree () {}
  ~PTree () { this->root.deleteAllNode (); }
  T * fetch (void * key, size_t len);
  T * lookup (void * key, size_t len);
  T * search (void * key, size_t len);
  bool remove (void * key, size_t len);
  bool insert (void * key, size_t len, T * p);

  void feInit ();
  void feNext ();
  bool feEnd ();
  T * feGet ();
};


//=========================================================================
template<class S> class PTreeNode 
{
  friend class PTree<S>;

private:
  u_int8_t *key;
  int keylen;
  S * data;
  bool alloc;
  PTreeNode * parent;
  PTreeNode * link[2];
  static int nodeCount ;
  static const int DEBUG_PTREE_NODE = false;

  void setKey (u_int8_t * key, int len);
  void setChild (PTreeNode * pnode);
  void unsetChild (PTreeNode * pnode);
  void deleteAllNode (void);
  int getDataCount () { return this->dataCount; }

  // OCTET_SPACE() returns the number of bytes neccessary to store the bits 
  inline int OCTET_SPACE(int bits) { return ((((bits)-1)/8)+1); }
  inline u_int8_t CHECK_BIT(u_int8_t *K, int L) 
  { return ((((u_int8_t *)(K))[(L)/8] >> (7 - (L)%8)) & 1); }

public:  
  PTreeNode (u_int8_t * _key = NULL, int _keylen = 0) : 
    key (NULL), keylen (0), data (NULL), alloc (NULL), parent (NULL)
  {
    debug (DEBUG_PTREE_NODE, "create PTreeNode (keylen = %d)", keylen);

    this->link [0] = NULL;
    this->link [1] = NULL;

    if (_key)
      this->setKey (_key, _keylen);

    nodeCount++;
  }; 

  ~PTreeNode ()
  {
    debug (DEBUG_PTREE_NODE, "destroy PTreeNode (keylen = %d)", this->keylen);

    if (this->data && this->alloc)
      delete this->data;
    if (this->key)
      free (this->key);

    nodeCount--;
  }

  static int getNodeCount () { return nodeCount; }
};

template<class S>
int PTreeNode<S>::nodeCount = 0;






// ==============================================================================
//  PTree
// ==============================================================================

template<class T>
T * PTree<T>::fetch (void * _key, size_t _len)
{
  u_int8_t * key = static_cast<u_int8_t*>(_key);
  int keyLen = static_cast<int>(_len * 8);

  PTreeNode<T> * bp, * mp; /* branch point, matched point */
  PTreeNode<T> * t = NULL; /* target node */
  assert (key && keyLen > 0);

  for (bp = &this->root, mp = NULL; 
       bp != NULL && MATCH_KEY (bp->key, key, bp->keylen);
       bp = bp->link [CHECK_BIT (key, bp->keylen)])
    {
      mp = bp;

      if (bp->keylen >= keyLen)
	break;
    }

  if (bp == NULL)
    bp = mp;
  
  if (bp->keylen == keyLen && MATCH_KEY (bp->key, key, bp->keylen))
    {
      t = bp;
    }
  else
    {
      t = new PTreeNode<T> (key, keyLen);
      this->branchNode (bp, t);
    }

  if (t->data == NULL)
    {
      t->data = new T ;
      t->alloc = true;
      this->dataCount++;
    }
  
  return t->data;
  // return this->root.fetch ((u_int8_t*)key, (int)(len * 8));
}

template<class T>
T * PTree<T>::lookup (void * _vkey, size_t _len)
{
  u_int8_t * argKey = static_cast<u_int8_t*>(_vkey);
  int argKeylen = static_cast<int>(_len * 8);

  PTreeNode<T> * n;
  assert (argKey && argKeylen > 0);

  if (argKeylen == 0)
    return NULL;

  for (n = &this->root; 
       n && argKeylen >= n->keylen; 
       n = n->link [CHECK_BIT (argKey, n->keylen)])
    {
      if (n->keylen == argKeylen && MATCH_KEY (n->key, argKey, n->keylen))
	return n->data;

      if (n->keylen > argKeylen)
	break;
    }

  return NULL;
  // return this->root.lookup ((u_int8_t*)key, (int)(len * 8));
}

template<class T>
T * PTree<T>::search (void * _key, size_t _len)
{
  u_int8_t * argKey = static_cast<u_int8_t*>(_key);
  int argKeylen = static_cast<int>(_len * 8);

  PTreeNode<T> * n;
  assert (argKey && argKeylen > 0);

  if (argKeylen == 0)
    return NULL;

  T * tgt = NULL;
  for (n = &this->root; n && argKeylen >= n->keylen; 
       n = n->link [CHECK_BIT (argKey, n->keylen)])
    {
      if (n->keylen > 0 && ! MATCH_KEY (n->key, argKey, n->keylen))
	break;
	
      if (n->data)
	tgt = n->data;

      if (n->keylen > argKeylen)
	break;
    }

  return tgt;
  // return this->root.search ((u_int8_t*)key, (int)(len * 8));
}

template<class T>
bool PTree<T>::remove (void * _key, size_t _len)
{
  u_int8_t * argKey = static_cast<u_int8_t*>(_key);
  int argKeylen = static_cast<int>(_len * 8);

  PTreeNode<T> * n, * t = NULL;
  assert (argKey && argKeylen > 0);

  for (n = &this->root; n && argKeylen >= n->keylen; 
       n = n->link [CHECK_BIT (argKey, n->keylen)])
    {
      if (n->keylen == argKeylen && MATCH_KEY (n->key, argKey, n->keylen))
	{
	  t = n;
	  break;
	}
    }

  if (! t || !t->parent)
    return false; /* nothig remove or this node is root */

  this->deleteNode (t);

  // data counter that root node have
  this->dataCount--;
  assert (this->dataCount >= 0);

  return true;
  // return this->root.remove ((u_int8_t*)key, (int)(len * 8));
}

template<class T>
bool PTree<T>::insert (void * _key, size_t _len, T * p)
{
  u_int8_t * argKey = static_cast<u_int8_t*>(_key);
  int argKeylen = static_cast<int>(_len * 8);

  PTreeNode<T> * bp, * mp; /* branch point, matched point */
  PTreeNode<T> * t = NULL; /* target node */
  assert (argKey && argKeylen > 0);

  for (bp = &this->root, mp = NULL; 
       bp != NULL && MATCH_KEY (bp->key, argKey, bp->keylen);
       bp = bp->link [CHECK_BIT (argKey, bp->keylen)])
    {
      mp = bp;

      if (bp->keylen >= argKeylen)
	break;
    }

  if (bp == NULL)
    bp = mp;
  
  if (bp->keylen == argKeylen && MATCH_KEY (bp->key, argKey, bp->keylen))
    {
      t = bp;

      if (t->data)
	return false;
    }
  else
    {
      t = new PTreeNode<T> (argKey, argKeylen);
      this->branchNode (bp, t);
    }

  assert (t->data == NULL);
  t->data = p;
  this->dataCount++;

  return true;
  // return this->root.insert ((u_int8_t*)key, (int)(len * 8), p);
}

template <class T>
void PTree<T>::deleteNode (PTreeNode<T> * t)
{
  int st = LINK_NULL;
  bool delNode = true;
  PTreeNode<T> * parent = t->parent;

  if (! t->parent)
    return ; /* this is root node */

  st |= (t->link[0] ? LINK_0_OK : LINK_NULL);
  st |= (t->link[1] ? LINK_1_OK : LINK_NULL);

  switch (st)
    {
    case LINK_0_OK: t->parent->setChild (t->link[0]); break;
    case LINK_1_OK: t->parent->setChild (t->link[1]); break;
    case LINK_NULL: t->parent->unsetChild (t); break;
    case LINK_BOTH_OK:
      delete t->data;
      t->data = NULL;
      delNode = false;
      break;
    }

  if (delNode)
    {
      delete t;
      if (parent->data == NULL &&
	  (parent->link [0] == NULL || parent->link [1] == NULL))
	this->deleteNode (parent);
    }

  return ;
}


template <class T>
void PTree<T>::branchNode (PTreeNode<T> * a, PTreeNode<T> * b)
{
  int len, min, i;
  PTreeNode<T> * parent, * branch, * child;

  assert (b != NULL);

  /* search different point between keys */
  min = MIN (a->keylen, b->keylen);
  for (i = 0, len = 0; i < (min/8) && a->key[i] == b->key[i] ; i++)
    len += 8;
  for (; len < min; len++)
    if (CHECK_BIT (a->key, len) != CHECK_BIT (b->key, len))
      break;

  assert (len != a->keylen || len != b->keylen);

  /* select branch node */
  if (a->parent != NULL || b->parent != NULL)
    parent = (a->parent != NULL) ? a->parent : b->parent;
  else
    parent = NULL;

  // ptree = (a->tree != NULL) ? a->tree : b->tree;

  if (len == a->keylen || len == b->keylen)
    {
      branch = (a->keylen < b->keylen) ? a : b;
      child  = (a->keylen < b->keylen) ? b : a;
      branch->setChild (child);
    }
  else
    {
      branch = new PTreeNode<T> (a->key, len);
      branch->setChild (a);
      branch->setChild (b);
    }

  if (parent)
    parent->setChild (branch);

  return;
}



// ==============================================================================
//  PTreeNode
// ==============================================================================

template <class S>
void PTreeNode<S>::setKey (u_int8_t * _key, int _keylen)
{
  if (this->key)
    free (this->key);
  
  if (0 < (this->keylen = _keylen))
    {
      this->key = (u_int8_t*) calloc (OCTET_SPACE (_keylen) + 1, sizeof(u_int8_t));
      memcpy (this->key, _key, OCTET_SPACE (_keylen));
    }
  else
    this->key = NULL;
} 


template <class S>
void PTreeNode<S>::setChild (PTreeNode * child)
{
  assert (child);

  this->link [CHECK_BIT (child->key, this->keylen)] = child;
  child->parent = this;
  return;
}

template <class S>
void PTreeNode<S>::unsetChild (PTreeNode * child)
{
  assert (child);
  this->link [CHECK_BIT (child->key, this->keylen)] = NULL;
  child->parent = NULL;
  return;
}



template <class S>
void PTreeNode<S>::deleteAllNode (void)
{
  if (this->link[0])
    {
      this->link[0]->deleteAllNode ();
      assert (this->link[0]->link[0] == NULL &&
	      this->link[0]->link[1] == NULL);
      delete this->link[0];
      this->link[0] = NULL;
    }
  if (this->link[1])
    {
      this->link[1]->deleteAllNode ();
      assert (this->link[1]->link[0] == NULL &&
	      this->link[1]->link[1] == NULL);
      delete this->link[1];
      this->link[1] = NULL;
    }

  return ;
}

template<class T>
void PTree<T>::feInit ()
{
  this->ptr = this->reHead (&this->root);
  return ;
}

template<class T>
PTreeNode<T> * PTree<T>::reHead (PTreeNode<T> * p)
{
  while (p->link[0] || p->link[1])
    {
      while (p->link[0])
	p = p->link[0];

      while (p->link[1])
	p = p->link[1];
    }

  return p;
}

template<class T>
void PTree<T>::feNext ()
{
  if (this->ptr == NULL)
    return ;

  PTreeNode<T> * next = this->ptr->parent;
  if (next == NULL || next->parent == NULL)
    {
      this->ptr = NULL;
      return ;
    }

  if (next->link[1] != this->ptr)
    next = this->reHead (next->link[1]);

  this->ptr = next;

  if (this->ptr->data == NULL)
    this->feNext ();

  return ;
}

template<class T>
bool PTree<T>::feEnd ()
{
  return ((this->ptr == NULL || this->ptr == &this->root) ? true : false);
}
 
template<class T>
T * PTree<T>::feGet ()
{
  if (this->ptr == NULL)
    return NULL;
  else
    return this->ptr->data;
}


// **********************************************************************
// * Hash
// **********************************************************************

template <class T> class HashNode;

template <class T> class Hash : public Table<T>
{
private:
  static const bool DEBUG = false;
  long long int debugLoopCounter [20];

  size_t size;
  HashNode<T> * hashTable;
  HashNode<T> * ptr; // foreach 
  size_t cur;           // foreach
  int (*hashFunc) (void * key, size_t len);
  int defltHash (void * key, size_t len);
  void attachNode (HashNode<T> * prev, HashNode<T> * node);
  void detachNode (HashNode<T> * node);
  inline int hash (void * key, size_t len) 
  { 
    if (this->hashFunc)
      return this->hashFunc (key, len) % this->size; 
    else 
      return this->defltHash (key, len) % this->size;
  }

public:
  Hash (size_t argSize, int (*hf)(void *, size_t) = NULL)
    : size (argSize), ptr (NULL), cur(0),  hashFunc (hf) {
    this->hashTable = new HashNode<T> [this->size];
    memset (this->debugLoopCounter, 0, sizeof (this->debugLoopCounter));
  }
  ~Hash ()
  {
    for (int n = 0; n < 20; n++)
      debug (DEBUG, "loop [%d] = %lld", n, this->debugLoopCounter [n]);

    for (size_t i = 0; i < this->size; i++)
      {
	HashNode<T> *p, *base = &this->hashTable[i];
	for (p = base->next; p != base; p = base->next)
	  {
	    this->detachNode (p);
	    delete p;
	  }
      }

    delete [] this->hashTable;
  }

  T * fetch (void * key, size_t len);
  T * lookup (void * key, size_t len);
  T * search (void * key, size_t len);
  bool remove (void * key, size_t len);
  bool insert (void * key, size_t len, T * p);

  int getNodeCount () { return this->hashTable[0].getNodeCount (); }

  void feInit ();
  void feNext ();
  bool feEnd ();
  T * feGet ();
};

template <class T> class HashNode
{
  friend class Hash<T>;

private:
  T * data;
  void * keyData;
  size_t keySize;
  HashNode<T> * next, * prev;
  static int nodeCount;
  bool alloc;

  inline void setKey (void * key, size_t size);
  inline void unsetKey ();
  inline bool matchKey (void * key, size_t size)
  { return (size == this->keySize && memcmp (key, this->keyData, size) == 0); }
  inline void setData (T * p) { this->data = p; }
  inline T * getData () { return this->data; }
  inline T * createData () 
  { this->alloc = true; return (this->data = new T ());  }
  inline void destroyData () { if (this->data && this->alloc) delete this->data; }

public:
  HashNode () : data (NULL), keyData (NULL), keySize (0), next (this), prev (this), alloc (false) 
  { this->nodeCount++; }
  ~HashNode () { 
    this->unsetKey (); 
    this->destroyData ();
    this->nodeCount--;
  }  
  int getNodeCount () { return nodeCount; }
};

template<class T>
int HashNode<T>::nodeCount = 0;


template<class T> T * Hash<T>::fetch (void * key, size_t len)
{
  HashNode<T> *p, * base = &(this->hashTable[this->hash (key, len)]);
  int i = 0;
  for (p = base->next ; p != base; p = p->next)
    {
      i++;
      if (p->matchKey (key, len))
	return p->data;
    }

  i = (i >= 20) ? 19 : i;
  this->debugLoopCounter [i]++;

  this->dataCount++;
  p = new HashNode<T>;
  p->setKey (key, len);
  this->attachNode (base, p);  
  return p->createData ();
}

template<class T> T * Hash<T>::lookup (void * key, size_t len)
{
  HashNode<T> *p, * base = &(this->hashTable[this->hash (key, len)]);
  int i = 0;
  for (p = base->next ; p != base; p = p->next)
    {
      i++;
      if (p->matchKey (key, len))
	break;
    }

  i = (i >= 20) ? 19 : i;
  this->debugLoopCounter [i]++;
  
  return (p == base) ? NULL : p->data;
}

template<class T> T * Hash<T>::search (void * key, size_t len)
{
  assert (0); // Hash table is not supported longest match
  return NULL;
}

template<class T> bool Hash<T>::remove (void * key, size_t len)
{
  HashNode<T> *p, * base = &(this->hashTable[this->hash (key, len)]);
  for (p = base->next ; p != base; p = p->next)
    {
      if (p->matchKey (key, len))
	{
	  this->dataCount--;
	  this->detachNode (p);
	  delete p;
	  return true;
	}
    }
  
  return false;
}

template<class T> bool Hash<T>::insert (void * key, size_t len, T * obj)
{
  HashNode<T> *p, * base = &(this->hashTable[this->hash (key, len)]);
  int i = 0;
  for (p = base->next ; p != base; p = p->next)
    {
      i++;
      if (p->matchKey (key, len))
	return false;
    }

  i = (i >= 20) ? 19 : i;
  this->debugLoopCounter [i]++;

  this->dataCount++;
  p = new HashNode<T>;
  p->setKey (key, len);
  p->setData (obj);
  this->attachNode (base, p);
  return true;
}

static const u_int32_t mask[] = { 0x00000000, 0x000000ff, 0x0000ffff, 0x00ffffff };

template<class T> int Hash<T>::defltHash (void * key, size_t len)
{
  assert (len > 0);
  u_int32_t p = 0xFEEDCAFE;
  int r;
  int n = static_cast<int> (len);
  u_int32_t * k = static_cast<u_int32_t*> (key);
  for (; n >= 4; n -= 4, k++)
    p ^= *k;

  p ^= (*k & mask[n]);
  r = static_cast<int> (p * 0xbee7);
  return (r > 0 ? r : -r);
}

template<class T> void Hash<T>::attachNode (HashNode<T> * prev, HashNode<T> * node)
{
  HashNode<T> * next = prev->next;
  next->prev = node;
  prev->next = node;
  node->prev = prev;
  node->next = next;
  return ;
}
 
template<class T> void Hash<T>::detachNode (HashNode<T> * node)
{
  HashNode<T> * next = node->next;
  HashNode<T> * prev = node->prev;
  next->prev = prev;
  prev->next = next;
  node->next = node->prev = node;
  return ;
}


template<class T> void HashNode<T>::setKey (void * key, size_t len)
{
  this->unsetKey ();
  this->keyData = malloc (len);
  this->keySize = len;
  memcpy (this->keyData, key, this->keySize);
  return ;
}

template<class T> void HashNode<T>::unsetKey ()
{
  if (this->keyData)
    {
      free (this->keyData);
      this->keyData = NULL;
      this->keySize = 0;
    }
}


template<class T>
void Hash<T>::feInit ()
{
  this->cur = 0;
  this->ptr = NULL;
  this->feNext ();
}

template<class T>
void Hash<T>::feNext ()
{
  if (this->ptr != NULL && this->ptr->next != &this->hashTable[this->cur])
    {
      this->ptr = this->ptr->next;
    }
  else
    {
      this->ptr = NULL;
      while (this->cur < this->size)
	{
	  this->cur++;
	  if (this->hashTable[this->cur].next != &this->hashTable[this->cur])
	    {
	      this->ptr = this->hashTable[this->cur].next;
	      break;
	    }
	}
    }

  return ;
}

template<class T>
bool Hash<T>::feEnd ()
{
  return (this->ptr == NULL ? true : false);
}
 
template<class T>
T * Hash<T>::feGet ()
{
  if (this->ptr)
    return this->ptr->data;
  else
    return NULL;
}

#endif /* __PTREE_H__ */

